package leetcode;

import java.util.Arrays;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-12-16 16:36
 **/
public class LeetCode581 {

    // 一次遍历
    public int findUnsortedSubarray(int[] nums) {
        int n = nums.length;
        int maxLeft = Integer.MIN_VALUE;
        int right = -1;
        int minRight = Integer.MAX_VALUE;
        int left = -1;
        for (int i = 0; i < n; i++) {
            //如果左边的最大值小于当前值,更新右边界,否则更新最大值
            if (maxLeft > nums[i]) {
                right = i;
            } else {
                maxLeft = nums[i];
            }

            //如果右边的最小值大于当前值,更新左边界,否则更新最小值
            if (minRight < nums[n - i - 1]) {
                left = n - i - 1;
            } else {
                minRight = nums[n - i - 1];
            }
        }

        //如果右边界为-1说明数组本来就是升序的,否则返回需要排序的子数组的长度。
        return right == -1 ? 0 : right - left + 1;
    }

    //排序
    /*public int findUnsortedSubarray(int[] nums) {
        if (isSorted(nums)) {
            return 0;
        }

        int n = nums.length;
        int[] temp = new int[n];
        System.arraycopy(nums, 0, temp, 0, n);
        Arrays.sort(temp);
        int left = 0;
        while (nums[left] == temp[left]) {
            ++left;
        }

        int right = n - 1;
        while (nums[right] == temp[right]) {
            --right;
        }

        return right - left + 1;

    }

    //判断数组是否有序
    boolean isSorted(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] < nums[i - 1]) {
                return false;
            }
        }

        return true;
    }*/

    public static void main(String[] args) {
        LeetCode581 code = new LeetCode581();
        System.out.println(code.findUnsortedSubarray(new int[]{2, 4, 6, 8, 10, 1, 3, 5, 7, 9}));
    }

}
